/*
 * Saphre - Suffix Arrays for Phrase Extraction
 * Copyright (C) 2013 
 * Dale Gerdemann - Tübingen, Germany 
 * Niko Schenk - Frankfurt am Main, Germany
 * All rights reserved.
 *
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 *
 */
package util;

import saphre.core.Store;
import saphre.core.SuffixArray;
import util.sorting.Multiset;

import java.util.Set;
import java.util.TreeSet;
import java.util.PriorityQueue;
import util.tokenization_io.BoundarySymbols;

/**
 * An "Bisected" Interval class. What this means is that the Interval stores
 * it's own midpoint. The purpose is to have a more heavyweight interval class
 * that can be used when efficiency is not an issue.
 *
 * @author Dale Gerdemann
 */
public class BiInterval {

    Store store;
    SuffixArray sa;
    /**
     * left boundary of interval
     */
    private int lb;
    /**
     * right boundary of interval
     */
    private int rb;
    int mid;
    int lcp;

    public BiInterval(Interval inter, SuffixArray sa, Store store) {
        lb = inter.lb;
        rb = inter.rb;
        this.sa = sa;
        this.store = store;
        // System.out.println(sa.top);
        mid = sa.cldtab[lb];
        if (mid <= lb || mid > rb) {
            mid = sa.cldtab[rb];
        }
        lcp = sa.getLcp(mid);
    }

    public BiInterval(int lb, int rb, SuffixArray sa, Store store) {
        this.lb = lb;
        this.rb = rb;
        this.sa = sa;
        this.store = store;
        mid = sa.cldtab[lb];
        if (mid <= lb || mid > rb) {
            mid = sa.cldtab[rb];
        }
        lcp = sa.getLcp(mid);
    }

    public Interval interval() {
        return new Interval(lb, rb);
    }

    public Store store() {
        return store;
    }

    public SuffixArray sa() {
        return sa;
    }

    public int lb() {
        return lb;
    }

    public int rb() {
        return rb;
    }

    public int mid() {
        return mid;
    }

    public int lcp() {
        return lcp;
    }

    /**
     * @return true if interval is of length 1
     */
    public boolean trivial() {
        return lb == rb;
    }

    /**
     * @return true if interval is not length 1
     */
    public boolean nonTrivial() {
        return lb != rb;
    }

    /**
     * @return true if interval is of length 0
     */
    public boolean empty() {
        return rb < lb;
    }

    /**
     * @return the term frequency for the interval
     */
    public int tf() {
        return rb - lb + 1;
    }

    // Naive method for document frequency. Doubles the running time
    // of td (top down interval tree traversal). But this is not a
    // major problem since td is so fast. The real bottlenecks are
    // extendend suffix array construction, and especially
    // construction of the new child table. Still the plan is to
    // improve this for a future version.
    /**
     * @return the document frequency for the interval
     */
    public int df() {
        Set<Integer> d = new TreeSet<Integer>();
        for (int i = lb; i <= rb; i++) {
            d.add(store.docNum(sa.suftab[i]));
        }
        return d.size();
    }

    /**
     * @return the document distribution for the interval
     */
    public Multiset docDist() {
        Multiset d = new Multiset();
        for (int i = lb; i <= rb; i++) {
            d.incr(store.docNum(sa.suftab[i]));
        }
        return d;
    }

    public int compareTo(Interval other) {
        if (lb < other.lb) {
            return -1;
        } else if (lb > other.lb) {
            return 1;
        } else if (rb < other.rb) {
            return -1;
        } else if (rb > other.rb) {
            return 1;
        } else {
            return 0;
        }
    }

    public boolean equals(Interval other) {
        return (other != null) && lb == other.lb && rb == other.rb;
    }

    public boolean contains(Interval other) {
        return lb <= other.lb && rb >= other.rb;
    }

    public String toRepString() {
        if (empty()) {
            return "_";
        } else {
            StringBuilder sb = new StringBuilder();
            sb.append("(").append(lb).append(",");
            sb.append(rb).append(")");
            return sb.toString();
        }
    }

    public String toString() {
        int loc = sa.getSuftab()[lb];
        return store.toStringL(loc, lcp);
    }

    public String toRevString() {
        SuffixArray pa = sa;
        int loc = pa.getSuftab()[lb];
        return store.toStringLRev(loc, lcp);
    }

    String spaces(int n) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 2 * n; i++) {
            sb.append(' ');
        }
        return sb.toString();
    }

    public int[] toArray() {
        int loc = sa.getSuftab()[lb];
        return store.toArrayL(loc, lcp);
    }

    public int[] toRevArray() {
        SuffixArray pa = sa;
        int loc = pa.getSuftab()[lb];
        return store.toArrayLRev(loc, lcp);
    }

    public int pos(int[] suffixTable) {
        return sa.suftab[lb];
    }

    public BiInterval left() {
        return new BiInterval(lb, mid - 1, sa, store);
    }

    public BiInterval right() {
        return new BiInterval(mid, rb, sa, store);
    }

    public Multiset following() {
        Multiset result = new Multiset();
        //        int lcp = lcp(mid, sa.lcptab);
        for (int i = lb; i <= rb; i++) {
            result.incr(store.text[sa.getSuftab()[i] + lcp]);
        }
        return result;
    }

    public Multiset preceding() {
        Multiset result = new Multiset();
        for (int i = lb; i <= rb; i++) {
            result.incr(store.text[sa.getSuftab()[i] - 1]);
        }
        return result;
    }

    public int compare1(int i, int j, int length) {

        int followI = store.text[sa.getSuftab()[i] + length];
        int followJ = store.text[sa.getSuftab()[j] + length];

        if (followI < followJ) {
            return -1;
        } else if (followI > followJ) {
            return 1;
        }

        int precedeI = store.text[sa.getSuftab()[i] - 1];
        int precedeJ = store.text[sa.getSuftab()[j] - 1];
        if (precedeI < precedeJ) {
            return -1;
        } else if (precedeI > precedeJ) {
            return 1;
        }
        return 0;
    }

    public PriorityQueue<StringWithScore> toStringSorted1(BoundarySymbols bsym) {
        PriorityQueue<StringWithScore> contexts =
                new PriorityQueue<StringWithScore>();
        int[] sorted = sort1();
        int pred = sorted[0];
        Multiset follow = following();
        Multiset precede = preceding();
        int followId = store.text[sa.getSuftab()[pred] + lcp];
        String followWord = store.toString(followId);
        int precedeId = store.text[sa.getSuftab()[pred] - 1];
        String precedeWord = store.toString(precedeId);
        int c1 = follow.cnt(followId);
        int c2 = precede.cnt(precedeId);
        // System.out.print(precedeWord + "~" + followWord);
        double tf = (double) tf();
        double expected = (c1 * c2) / tf;
        int occurrences = 1;
        for (int i = 1; i < sorted.length; i++) {


            int e = sorted[i];

            if (compare1(pred, e, lcp) == 0) {
                occurrences++;
                continue;
            }


            // System.out.println(": " + occurrences/expected);

            double score = occurrences / expected;
            if (score > 0.95
                    && !bsym.userSentinel(precedeId)
                    && !bsym.userSentinel(followId)) {
                StringWithScore elem =
                        new StringWithScore(precedeId, followId,
                        occurrences / expected);
                //System.out.println(elem.toString(store));
                contexts.add(elem);
            }

            occurrences = 1;
            followId = store.text[sa.getSuftab()[e] + lcp];
            followWord = store.toString(followId);
            precedeId = store.text[sa.getSuftab()[e] - 1];
            precedeWord = store.toString(precedeId);
            c1 = follow.cnt(followId);
            c2 = precede.cnt(precedeId);

            // System.out.print(precedeWord + "~" + followWord);
            pred = e;
        }

        double score = occurrences / expected;
        if (score > 0.95
                && !bsym.userSentinel(precedeId)
                && !bsym.userSentinel(followId)) {
            StringWithScore elem =
                    new StringWithScore(precedeId, followId,
                    occurrences / expected);
            contexts.add(elem);
        }
        return contexts;
    }

    public int[] sort1() {
        return sort1(lcp);
    }

    public int[] sort1(int length) {
        if (trivial()) {
            int[] result = {lb};
            return result;
        } else {
            int[] s1 = left().sort1(length);

            int[] s2 = right().sort1(length);
            int[] result = new int[tf()];
            merge1(s1, s2, result, length);
            /*
             System.out.print("s1:  ");
             System.out.println(Arrays.toString(s1));
             System.out.print("s2:  ");
             System.out.println(Arrays.toString(s2));
             System.out.print("resut:  ");
             System.out.println(Arrays.toString(result));
             */
            return result;
        }
    }

    private void merge1(int[] s1, int[] s2, int[] result, int length) {
        int p1 = 0;
        int p2 = 0;
        int k = 0;
        while (p1 < s1.length && p2 < s2.length) {
            int comp = compare1(s1[p1], s2[p2], length);
            if (comp <= 0) {
                result[k] = s1[p1];
                p1++;
            } else {
                result[k] = s2[p2];
                p2++;
            }
            k++;
        }
        if (p1 == s1.length) {
            add(s2, result, p2, k);
        }
        if (p2 == s2.length) {
            add(s1, result, p1, k);
        }
    }

    private void add(int[] s, int[] r, int p, int k) {
        while (p < s.length) {
            r[k] = s[p];
            p++;
            k++;
        }
    }

    public int last() {
        return store.text[sa.getSuftab()[lb] + lcp - 1];
    }
}
